/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28318
 * Date: 2025-10-17
 * Time: 16:38
 */

import java.util.*;

/**
 * 进程类：封装进程的所有属性
 */
class Process {
    int pid;          // 进程ID
    int arrivalTime;  // 到达时间
    int burstTime;    // 预计运行时间
    int startTime;    // 开始执行时间（初始化为-1，表示未开始）
    int completionTime;  // 完成时间（初始化为-1，表示未完成）
    int turnaroundTime;  // 周转时间（TAT = CT - AT）
    int waitingTime;     // 等待时间（WT = TAT - BT）
    int responseTime;    // 响应时间（RT = ST - AT）
    int remainingTime;   // 剩余运行时间（用于RR算法）
    boolean isCompleted; // 是否完成（初始化为false）
    boolean isInQueue;   // 是否已加入就绪队列（用于RR算法，避免重复加入）

    // 构造方法：初始化进程的核心属性（PID、AT、BT）
    public Process(int pid, int arrivalTime, int burstTime) {
        this.pid = pid;
        this.arrivalTime = arrivalTime;
        this.burstTime = burstTime;
        this.remainingTime = burstTime; // 剩余时间初始化为运行时间
        this.startTime = -1;
        this.completionTime = -1;
        this.turnaroundTime = 0;
        this.waitingTime = 0;
        this.responseTime = 0;
        this.isCompleted = false;
        this.isInQueue = false;
    }

    // 重置进程状态（用于多组测试用例复用）
    public void reset() {
        this.remainingTime = burstTime;
        this.startTime = -1;
        this.completionTime = -1;
        this.turnaroundTime = 0;
        this.waitingTime = 0;
        this.responseTime = 0;
        this.isCompleted = false;
        this.isInQueue = false;
    }
}

/**
 * 调度器类：实现FCFS、SJF、RR三种调度算法
 */
class Scheduler {
    /**
     * 1. 先来先服务（FCFS）调度算法
     * @param processes 进程列表（需传入副本，避免修改原数据）
     * @return 调度后的进程列表（含计算完成的所有属性）
     */
    public static List<Process> fcfs(List<Process> processes) {
        // 复制进程列表（避免修改原测试用例数据）
        List<Process> fcfsProcesses = copyProcessList(processes);
        // 按到达时间升序排序，到达时间相同按PID升序排序
        fcfsProcesses.sort((p1, p2) -> {
            if (p1.arrivalTime != p2.arrivalTime) {
                return Integer.compare(p1.arrivalTime, p2.arrivalTime);
            } else {
                return Integer.compare(p1.pid, p2.pid);
            }
        });

        int currentTime = 0; // 当前时间
        for (Process p : fcfsProcesses) {
            // 如果进程到达时间晚于当前时间，CPU等待
            if (p.arrivalTime > currentTime) {
                currentTime = p.arrivalTime;
            }
            // 计算进程的核心属性
            p.startTime = currentTime;
            p.completionTime = p.startTime + p.burstTime;
            p.turnaroundTime = p.completionTime - p.arrivalTime;
            p.waitingTime = p.turnaroundTime - p.burstTime;
            p.responseTime = p.startTime - p.arrivalTime; // 非抢占式，RT=WT
            // 更新当前时间为进程完成时间
            currentTime = p.completionTime;
            p.isCompleted = true;
        }
        return fcfsProcesses;
    }

    /**
     * 2. 短作业优先（SJF）调度算法（非抢占式）
     * @param processes 进程列表
     * @return 调度后的进程列表
     */
    public static List<Process> sjf(List<Process> processes) {
        List<Process> sjfProcesses = copyProcessList(processes);
        int n = sjfProcesses.size();
        int currentTime = 0;
        int completed = 0; // 已完成进程数

        while (completed < n) {
            // 步骤1：找到所有「到达时间≤当前时间」且「未完成」的进程
            Process selectedProcess = null;
            for (Process p : sjfProcesses) {
                if (!p.isCompleted && p.arrivalTime <= currentTime) {
                    // 选择「运行时间最短」的进程；若相同，选到达时间早的；再相同选PID小的
                    if (selectedProcess == null) {
                        selectedProcess = p;
                    } else {
                        if (p.burstTime < selectedProcess.burstTime) {
                            selectedProcess = p;
                        } else if (p.burstTime == selectedProcess.burstTime) {
                            if (p.arrivalTime < selectedProcess.arrivalTime) {
                                selectedProcess = p;
                            } else if (p.arrivalTime == selectedProcess.arrivalTime) {
                                if (p.pid < selectedProcess.pid) {
                                    selectedProcess = p;
                                }
                            }
                        }
                    }
                }
            }

            // 步骤2：执行选中的进程（或CPU等待新进程到达）
            if (selectedProcess != null) {
                // 计算属性
                selectedProcess.startTime = currentTime;
                selectedProcess.completionTime = selectedProcess.startTime + selectedProcess.burstTime;
                selectedProcess.turnaroundTime = selectedProcess.completionTime - selectedProcess.arrivalTime;
                selectedProcess.waitingTime = selectedProcess.turnaroundTime - selectedProcess.burstTime;
                selectedProcess.responseTime = selectedProcess.startTime - selectedProcess.arrivalTime;
                // 更新状态
                selectedProcess.isCompleted = true;
                completed++;
                currentTime = selectedProcess.completionTime;
            } else {
                // 无就绪进程，CPU空闲，时间+1
                currentTime++;
            }
        }
        return sjfProcesses;
    }

    /**
     * 3. 时间片轮转（RR）调度算法（抢占式）
     * @param processes 进程列表
     * @param timeQuantum 时间片长度
     * @return 调度后的进程列表
     */
    public static List<Process> rr(List<Process> processes, int timeQuantum) {
        List<Process> rrProcesses = copyProcessList(processes);
        int n = rrProcesses.size();
        int currentTime = 0;
        int completed = 0;
        Queue<Process> readyQueue = new LinkedList<>(); // 就绪队列（循环队列）

        // 步骤1：初始化就绪队列（加入所有到达时间=0的进程）
        for (Process p : rrProcesses) {
            if (p.arrivalTime == 0) {
                readyQueue.add(p);
                p.isInQueue = true;
            }
        }

        while (completed < n) {
            // 步骤2：从就绪队列取进程执行（或等待新进程到达）
            if (!readyQueue.isEmpty()) {
                Process currentProcess = readyQueue.poll(); // 取出队首进程

                // 第一次执行时，记录开始时间和响应时间
                if (currentProcess.startTime == -1) {
                    currentProcess.startTime = currentTime;
                    currentProcess.responseTime = currentProcess.startTime - currentProcess.arrivalTime;
                }

                // 步骤3：确定本次执行时长（不超过时间片，不超过剩余运行时间）
                int executeTime = Math.min(timeQuantum, currentProcess.remainingTime);
                // 执行后更新剩余时间
                currentProcess.remainingTime -= executeTime;
                // 更新当前时间
                currentTime += executeTime;

                // 步骤4：检查是否有新进程到达（加入就绪队列）
                for (Process p : rrProcesses) {
                    if (!p.isCompleted && !p.isInQueue && p.arrivalTime <= currentTime) {
                        readyQueue.add(p);
                        p.isInQueue = true;
                    }
                }

                // 步骤5：判断进程是否完成
                if (currentProcess.remainingTime == 0) {
                    // 计算完成属性
                    currentProcess.completionTime = currentTime;
                    currentProcess.turnaroundTime = currentProcess.completionTime - currentProcess.arrivalTime;
                    currentProcess.waitingTime = currentProcess.turnaroundTime - currentProcess.burstTime;
                    currentProcess.isCompleted = true;
                    completed++;
                } else {
                    // 未完成，放回就绪队列队尾
                    readyQueue.add(currentProcess);
                }
            } else {
                // 就绪队列为空，CPU空闲，时间+1
                currentTime++;
                // 检查是否有新进程到达（避免遗漏）
                for (Process p : rrProcesses) {
                    if (!p.isCompleted && !p.isInQueue && p.arrivalTime <= currentTime) {
                        readyQueue.add(p);
                        p.isInQueue = true;
                    }
                }
            }
        }
        return rrProcesses;
    }

    /**
     * 辅助方法：复制进程列表（避免修改原数据）
     */
    private static List<Process> copyProcessList(List<Process> original) {
        List<Process> copy = new ArrayList<>();
        for (Process p : original) {
            copy.add(new Process(p.pid, p.arrivalTime, p.burstTime));
        }
        return copy;
    }

    /**
     * 辅助方法：计算平均性能指标（ATAT、AWT、ART）
     * @param processes 调度后的进程列表
     * @return 数组：[平均周转时间, 平均等待时间, 平均响应时间]
     */
    public static double[] calculateAverageMetrics(List<Process> processes) {
        int n = processes.size();
        double totalTAT = 0, totalWT = 0, totalRT = 0;
        for (Process p : processes) {
            totalTAT += p.turnaroundTime;
            totalWT += p.waitingTime;
            totalRT += p.responseTime;
        }
        return new double[]{
                totalTAT / n,   // 平均周转时间（ATAT）
                totalWT / n,    // 平均等待时间（AWT）
                totalRT / n     // 平均响应时间（ART）
        };
    }

    /**
     * 辅助方法：打印调度结果（进程详细信息+平均指标）
     * @param algorithm 算法名称
     * @param processes 调度后的进程列表
     */
    public static void printResult(String algorithm, List<Process> processes) {
        System.out.println("==================================== " + algorithm + " 调度结果 ====================================");
        System.out.printf("%-6s %-10s %-10s %-10s %-10s %-10s %-10s %-10s%n",
                "PID", "到达时间", "运行时间", "开始时间", "完成时间", "周转时间", "等待时间", "响应时间");
        for (Process p : processes) {
            System.out.printf("%-6d %-10d %-10d %-10d %-10d %-10d %-10d %-10d%n",
                    p.pid, p.arrivalTime, p.burstTime, p.startTime, p.completionTime,
                    p.turnaroundTime, p.waitingTime, p.responseTime);
        }
        // 计算并打印平均指标
        double[] averages = calculateAverageMetrics(processes);
        System.out.printf("%n平均周转时间（ATAT）：%.2f ms%n", averages[0]);
        System.out.printf("平均等待时间（AWT）：%.2f ms%n", averages[1]);
        System.out.printf("平均响应时间（ART）：%.2f ms%n%n", averages[2]);
    }
}

/**
 * 主类：设计测试用例、调用算法、输出结果
 */
public class ProcessSchedulingExperiment {
    public static void main(String[] args) {
        // 定义3组测试用例（符合实验方案要求）
        List<List<Process>> testCases = new ArrayList<>();

        // 测试用例1：常规场景（进程到达时间不同，运行时间长短不一）
        List<Process> testCase1 = new ArrayList<>();
        testCase1.add(new Process(1, 0, 10));
        testCase1.add(new Process(2, 2, 5));
        testCase1.add(new Process(3, 4, 3));
        testCase1.add(new Process(4, 6, 7));
        testCase1.add(new Process(5, 8, 2));
        testCases.add(testCase1);
        System.out.println("<>");

        // 测试用例2：短进程集中场景（大部分短进程，少数长进程）
        List<Process> testCase2 = new ArrayList<>();
        testCase2.add(new Process(1, 0, 20)); // 长进程
        testCase2.add(new Process(2, 1, 2));  // 短进程
        testCase2.add(new Process(3, 2, 3));  // 短进程
        testCase2.add(new Process(4, 3, 1));  // 短进程
        testCase2.add(new Process(5, 4, 2));  // 短进程
        testCase2.add(new Process(6, 5, 15)); // 长进程
        testCases.add(testCase2);
        System.out.println("<>");

        // 测试用例3：进程同时到达场景（所有进程AT=0，运行时间不同）
        List<Process> testCase3 = new ArrayList<>();
        testCase3.add(new Process(1, 0, 8));
        testCase3.add(new Process(2, 0, 4));
        testCase3.add(new Process(3, 0, 1));
        testCase3.add(new Process(4, 0, 6));
        testCase3.add(new Process(5, 0, 3));
        testCases.add(testCase3);

        // 定义RR算法的时间片长度（可调整观察影响）
        int timeQuantum = 2;
        System.out.println("<>");

        // 对每组测试用例执行三种算法并输出结果
        for (int i = 0; i < testCases.size(); i++) {
            List<Process> testCase = testCases.get(i);
            System.out.println("==================================== 测试用例 " + (i + 1) + " ====================================");

            // 1. FCFS算法
            List<Process> fcfsResult = Scheduler.fcfs(testCase);
            Scheduler.printResult("FCFS", fcfsResult);

            // 2. SJF算法
            List<Process> sjfResult = Scheduler.sjf(testCase);
            Scheduler.printResult("SJF", sjfResult);

            // 3. RR算法
            List<Process> rrResult = Scheduler.rr(testCase, timeQuantum);
            Scheduler.printResult("RR（时间片=" + timeQuantum + "）", rrResult);

            System.out.println("=======================================================================================\n");
            System.out.println("<>");

        }
    }
}